package question11_15;

import java.io.PrintStream;

/**
 * @description: 剪绳子
 * @author: jhy
 * @time: 2021/5/22 12:57
 */
public class Question14 {

    public static void main(String[] args) {

        Question14 quetion14 = new Question14();
        int i = quetion14.cutRope(8);
        System.out.println(i);

    }

    //dp：时间复杂度O(n^2)，空间复杂度：O(1)
    //输入的是绳子的长度
    public int cutRope(int target) {
        if(target < 2){
            return 0;
        }
        if(target == 2){
            return 1;
        }
        if(target == 3){
            return 2;
        }

        //设置dp数组
        int[] dp = new int[target + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;

        int max = 0;
        for(int i = 4;i <= target;i++){
            max = 0;
            for(int j = 1;j <= i/2;j++){
                max = Math.max(dp[j] * dp[i-j],max);
            }
            dp[i] = max;
        }
        return dp[target];
    }
}
